package com.wsx.third;

import java.util.ArrayList;
import java.util.List;

/**
 * Created by wangshunxi on 2022/6/2.
 * e-mail: wsr12240512@163.com
 * phone: 13388071923
 */

public class Main0282 {
    int count = 0;

    public static void main(String[] args) {
        Main0282 entry = new Main0282();
        entry.addOperators("012403", 6);
        System.out.println(entry.ans.toString());
        System.out.printf("总共dfs次数 ：【%s】", entry.count);
    }

    List<String> ans = new ArrayList<>();
    int n;
    int t;
    String s;
    public List<String> addOperators(String num, int target) {
        if(num.length() == 0) return ans;
        n = num.length();
        t = target;
        s = num;
        dfs(0,0,0,"");
        return ans;
    }
    void dfs(int index,long prev,long cur,String str){
        count++;
        System.out.printf("index:%s , prev:%s , cur:%s , str:%s", index, prev, cur, str);
        System.out.println();
        if(index == n){
            if(cur == t) ans.add(str);
            return;
        }
        //从index处开始循环 获取所有可能的值 index = 1 那么可能的值为 1 12 120 1203
        for(int i = index;i<n;++i){
            //遇到0开头，且位数大于0；0是合法 01不合法跳过
            if(i != index && s.charAt(index) == '0')break;
            //取下一个数字 例如1 12 120 1203
            long next = Long.parseLong(s.substring(index, i + 1));
            if(index == 0){
                //从起始处开始 设置初始值 下一个下标，当前的值作为下一次的上一值，表达式计算的当前值，表达式字符串
                dfs(i + 1,next,next,""+next);
            }else{
                //不是从起始处开始 穷举所有可能的符号
                //穷举+ 下一个的起始值（当前值+1），当前值为 +next（作为下一次dfs的前值），表达式计算的当前值=上次表达式计算的值+当前值，表达式字符串=上次表达式字符串的值+当前值的字符串拼接
                dfs(i + 1,next,cur + next,str + "+" + next);
                //穷举- 下一个的起始值（当前值+1），当前值为 -next（作为下一次dfs的前值），表达式计算的当前值=上一次表达式计算的值-当前值，表达式字符串=上次表达式字符串的值-当前值的字符串拼接
                dfs(i + 1,-next,cur - next,str + "-" + next);
                //穷举* 下一个的起始值（当前值+1），当前值为prev*next
                dfs(i + 1,prev * next, cur - prev + prev * next,str + "*" + next);
                // 5 , 0 , 7 , "0+1+2+4+0"
            }
        }
    }
}
